МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ "ЛЬВІВСЬКА ПОЛІТЕХНІКА"
Програмування задач обробки масивів даних
"Основи інформаційних технологій та програмування"
Затверджено
на засіданні кафедри
автоматизації теплових
і хімічних процесів
Протокол № 2 від 18 вересня 2008 р.
Львів 2008
Мета роботи: засвоєння типових алгоритмів та програмування задач об робки масивів даних.
Основні відомості для виконання обробки масивів
Для розв’язування задач, пов’язаних із перетворенням (обробкою) масивів необхідно вміти представити вихідну задачу як сукупність більш простих задач, розв’язання яких є відомим. Нижче будуть представлені фрагменти типових задач, необхідних для розв’язання індивідуальних завдань до КРР.
Як відомо, двовимірні масиви розмірністю NN мають головну і допоміжну діа гоналі.
EMBED Equation.DSMT4
Індекси елементів головної діагоналі EMBED Equation.DSMT4, як видно із представлення двови мірного масиву, є однаковими.
Індекси елементів ж допоміжної діагоналі міняються за іншим правилом. Знайдемо його.
У першому рядку ( індекс - 0) елемент допоміжної діагоналі є - EMBED Equation.DSMT4;
у другому рядку ( індекс - 1) елемент допоміжної діагоналі є - EMBED Equation.DSMT4;
у третьому рядку (індекс - 2) елемент допоміжної діагоналі є - EMBED Equation.DSMT4;
…
в останньому рядку (індекс - N-1) елемент допоміжної діагоналі є - EMBED Equation.DSMT4.
Таким чином, елемент допоміжної діагоналі, який знаходиться в і-му рядку можна записати так: EMBED Equation.DSMT4.
Отже, до елементів обох діагоналей можна отримати доступ (зчитати) в од ному циклі.
Для вибору елементів під головною діагоналлю достатньо зауважити, що спра ведливе співвідношення для індексів, які відповідають за рядки і стовпчики, а саме: EMBED Equation.DSMT4. Щоби вибрати елементи масиву над головною діагоналлю, необхідно щоби їх індекси задовольняли умову: EMBED Equation.DSMT4.
Для вибору елементів під допоміжною діагоналлю достатньо зауважити, що справедливе співвідношення для індексів, які відповідають за рядки і стовпчики, а саме: EMBED Equation.DSMT4. Щоби вибрати елементи масиву над допоміжною діагоналлю, необхідно щоби їх індекси задовольняли умову: EMBED Equation.DSMT4.
Для знаходження max/min значення вектора/масиву (вважаємо масив вже сфор мованим) приймають за max/min вектора/масиву відповідно його перший елемент (EMBED Equation.DSMT4). Далі з цим значенням порівнюють наступний елемент/елементи доти, поки не зустрінеться елемент, значення якого більше/менше за значення max/min і т.д., аж до кінця вектора/масиву. На рис.2 представлені фрагменти блок-схеми ал горитмів пошуку min та max відповідно для вектора і двовимірного масиву.
Рис.2. Фрагменти блок-схеми алгоритмів пошуку: а) min; б) max.
а)
б)
EMBED Visio.Drawing.6
Примітка: У випадку необхідності здійснювати пошук max/min з одночасним форму ванням масиву потрібно задати max і min в max=-1е10, а min=1е10.
Обмін значень змінних (наприклад, х і у), елементів рядків (наприклад, першого і сотого) чи стовпчиків масиву здійснюється за допомогою допоміжної комірки (в даному випадку ідентифікатор допоміжної змінної temp):
EMBED Equation.DSMT4 EMBED Equation.DSMT4
Фрагмент блок-схеми алгоритму обміну значень елементів першого і сотого рядків наведено на рис.3.
Рис.3. Фрагмент блок-схеми алгоритму обміну елементів рядків.
EMBED Visio.Drawing.6
Для формування вектора з елементів масиву за певною ознакою, необхідно використовувати індексну змінну, попередньо ініціалізовану (нулем чи -1), яку потрібно модифікувати (збільшити на 1) додаючи до вектора новий елемент. Якщо ж не модифіковувати індексної змінної формованого вектора, то наступні еле менти, які потрібно записати у вектор, почина ючи з другого, будуть записуватися в одну і ту ж (першу) комірку і при цьому затирати зна чення попередніх елементів.
Рис.4. Фрагменти блок-схем алгоритмів формування вектор...
